package com.sicheng.蓝桥.练习题;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/3/23 14:30
 */
public class 纸牌三角形 {
    /**
     * 标题：纸牌三角形
     * <p>
     * A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形(A按1计算)。要求每个边的和相等。
     * <p>
     * 下图就是一种排法(如有对齐问题，参看p1.png)。
     * <p>
     * A
     * <p>
     * 9 　6
     * <p>
     * 4 　　  8
     * <p>
     * 3   7    5    2
     * <p>
     * 这样的排法可能会有很多。
     * <p>
     * 如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？  144
     * 原文链接：https://blog.csdn.net/weixin_39972996/article/details/114548796
     */

    public static void main(String[] args) {
        dfs(9);
        System.out.println(count / 6);
    }

    private static final ArrayDeque<Integer> path = new ArrayDeque<>();

    private static final boolean[] used = new boolean[9];

    private static int count;

    public static void dfs(int n) {
        if (path.size() == 9) {
            if (check(new ArrayList<>(path))) {
                count++;
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (used[i - 1])
                continue;
            path.addLast(i);
            used[i - 1] = true;
            dfs(n);
            path.removeLast();
            used[i - 1] = false;
        }
    }

    private static boolean check(List<Integer> path) {
        int a = 0, b = 0, c = 0;
        for (int i = 0; i <= 3; i++) {
            a += path.get(i);
        }
        for (int i = 3; i <= 6; i++) {
            b += path.get(i);
        }

        for (int i = 6; i <= 9; i++) {
            c += path.get(i % 9);
        }

        return a == b && c == b;
    }
}
